package com.beikai.demo01.sort.impl;

import com.beikai.demo01.sort.ArrSort;

/**
 * Created with IntelliJ IDEA.
 *
 * @author : hanbeikai
 * Date: 2021/6/4 7:21 下午
 * Description: 快速排序
 */
public class KuaiSuSort extends ArrSort {

    /**
     * 快速排序 采用分治的思想
     * 递归的方式划分段落
     * 每个段落选取一个比较的值a,然后把这个数组中大于a的值放一边,小于的值放另一边
     * 只要划分的够细,递归完成后,每个锚点左边的都大于或小于右边的,则可以保证整个数组是有序的
     *
     * @param arr
     * @return
     */
    @Override
    public int[] sort(int[] arr) {
        return handle(arr, 0, arr.length - 1);
    }

    private int[] handle(int[] arr, int left, int right) {
        if (left < right){
          int index = getIndex(arr,left,right);
          handle(arr,left,index-1);
          handle(arr,index+1,right);
        }
        return arr;
    }

    /**
     * 获取锚点
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private int getIndex(int[] arr, int left, int right) {
        // 获取中间点
        int mid = arr[left];
        // 设置小于中间点的分界点
        int start = left + 1;
        // 保证只在left和right范围内进行比较
        for (int i = start; i <= right; i++) {
            // 如果当前元素大于小于中间点,则边界往后进一位,并且与边界点的位置替换
            if (arr[i] < mid){
                // 小于中间点的数与边界的数交换
                swap(arr,i,start);
                // 边界进1
                start++;
            }
        }
        // 中间点与边界左边的值进行替换位置
        swap(arr,left,start-1);
        // 返回小于中间点位置的右边界下标
        return start - 1;
    }
}
